﻿#define _CRT_SECURE_NO_WARNINGS 1

//#include <iostream>
//#include <vector>
//#include <algorithm>
//using namespace std;
//bool IsNo(vector<int>& v)
//{
//    sort(v.begin(), v.end());
//    for (int i = 2; i < v.size(); i++)
//    {
//        if (v[i - 1] == v[i] && v[i] != 0)
//        {
//            return true;;
//        }
//    }
//    return false;
//}
//int main()
//{
//    int n = 0;
//    int x = 0, count = 1;
//    vector<int> v;
//    cin >> n;
//    v.resize(n + 1);
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> v[i];
//        if (v[i] == i)
//        {
//            v[i] = 0;
//            x++;
//        }
//    }
//
//    if (IsNo(v))
//    {
//        cout << 0 << endl;
//    }
//    else
//    {
//        for (int i = 1; i <= x; i++)
//        {
//            count *= i;
//        }
//        cout << count << endl;
//    }
//    return 0;
//}


//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main()
//{
//    int n = 0;
//    int count = 0;
//    vector<int> a;
//    cin >> n;
//    a.resize(n);
//    for (int i = 0; i < n; i++)
//    {
//        cin >> a[i];
//    }
//
//    int flag = 0, res = 1;
//    for (int i = 1; i < n - 1; i++)
//    {
//        if (a[i] > a[i - 1] && a[i] > a[i + 1] || a[i] < a[i - 1] && a[i] < a[i + 1])
//        {
//            res++;
//            if (n - 3 != i) i++;
//        }
//    }
//    printf("%d\n", res);
//    return 0;
//}


//#include <iostream>
//using namespace std;
//
//int main()
//{
//    long long t, h, ans, two;
//    cin >> t;
//    while (t--)
//    {
//        ans = 0;
//        two = 1;
//        cin >> h;
//        while (h)
//        {
//            h -= two;
//            ans++;
//            if (h % (2 * two) == 0)
//            {
//                two *= 2;
//            }
//        }
//        cout << ans << endl;
//    }
//    return 0;
//}
